/**
 * @(#)LC17电话号码的字母组合.java, 9月 30, 2021.
 * <p>
 * Copyright 2021 fenbi.com. All rights reserved.
 * FENBI.COM PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.wxweven.algorithm.string;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wxweven
 */
public class LC17电话号码的字母组合 {

    /*
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     *
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     *
     * 示例 1：
     *
     * 输入：digits = "23"
     * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
     * 示例 2：
     *
     * 输入：digits = ""
     * 输出：[]
     * 示例 3：
     *
     * 输入：digits = "2"
     * 输出：["a","b","c"]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
     * 讲解：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/tong-su-yi-dong-dong-hua-yan-shi-17-dian-hua-hao-m/
     */

    //一个映射表，第二个位置是"abc“,第三个位置是"def"。。。
    //这里也可以用map，用数组可以更节省点内存
    private String[] map = {" ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    //最终输出结果的list
    private List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        //注意边界条件
        if (digits == null || digits.length() == 0) {
            return res;
        }

        iterStr(digits, new StringBuilder(), 0);
        return res;
    }

    //递归函数
    void iterStr(String str, StringBuilder builder, int index) {
        //递归的终止条件，注意这里的终止条件看上去跟动态演示图有些不同，主要是做了点优化
        //动态图中是每次截取字符串的一部分，"234"，变成"23"，再变成"3"，最后变成""，这样性能不佳
        //而用index记录每次遍历到字符串的位置，这样性能更好
        if (index == str.length()) {
            res.add(builder.toString());
            return;
        }
        //获取index位置的字符，假设输入的字符是"234"
        //第一次递归时index为0所以c=2，第二次index为1所以c=3，第三次c=4
        //subString每次都会生成新的字符串，而index则是取当前的一个字符，所以效率更高一点

        //map_string的下表是从0开始一直到9， c-'0'就可以取到相对的数组下标位置
        //比如c=2时候，2-'0'，获取下标为2,letter_map[2]就是"abc"
        // 当前位数字对应的字符串映射
        String dict = map[str.charAt(index) - '0'];
        //遍历字符串，比如第一次得到的是2，页就是遍历"abc"
        for (int i = 0; i < dict.length(); i++) {
            //调用下一层递归，用文字很难描述，请配合动态图理解
            builder.append(dict.charAt(i));
            //如果是String类型做拼接效率会比较低
            //iterStr(str, letter+map_string.charAt(i), index+1);
            iterStr(str, builder, index + 1);

            // 因为每轮递归共用的是一个buier，如果不删除，那么结果就是
            // ["ad","ade","adef","adefbd","adefbde","adefbdef","adefbdefcd","adefbdefcde","adefbdefcdef"]
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}
